package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * https://leetcode.com/problems/house-robber-ii/
 * see 198 213 337
 *
 * @author tzp
 * @since 2020/9/15
 */
public class LC213 implements DynamicProblem {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        //0不抢当前, 1抢当前, 这俩标志位和198里一样, 算法也一样.
        //'2-不抢当前不抢0', '3抢当前不抢0'
        int[][] cache = new int[nums.length][4];

        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                cache[0][0] = 0;
                cache[0][1] = nums[0];
                cache[0][2] = 0;
                cache[0][3] = 0;//?
            } else if (i == 1) {
                cache[i][0] = nums[0];
                cache[i][1] = nums[1];
                cache[i][2] = 0;
                cache[i][3] = nums[1];
            } else {
                cache[i][0] = Math.max(cache[i - 1][0], cache[i - 1][1]);
                cache[i][1] = nums[i] + cache[i - 1][0];
                cache[i][2] = Math.max(cache[i - 1][2], cache[i - 1][3]);
                cache[i][3] = nums[i] + cache[i - 1][2];
            }
        }
        return Math.max(cache[nums.length - 1][0], cache[nums.length - 1][3]);
    }

    public static void main(String[] args) {
        System.out.println(new LC213().rob(new int[]{2, 7, 9, 3, 1}));
        System.out.println(new LC213().rob(new int[]{1, 2, 3, 1}));
        System.out.println(new LC213().rob(new int[]{2, 3, 2}));
        System.out.println(new LC213().rob(new int[]{1, 2, 3, 1}));
    }
}
